package random;

import java.util.*;

/**
 * 猜字谜
 *
 * 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
 * 字谜的迷面puzzle 按字符串形式给出，如果一个单词word符合下面两个条件，那么它就可以算作谜底：
 * 单词word中包含谜面puzzle的第一个字母。
 * 单词word中的每一个字母都可以在谜面puzzle中找到。
 * 例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；
 * 而 "beefed"（不含字母 "a"）以及"based"（其中的 "s" 没有出现在谜面中）。
 * 返回一个答案数组answer，数组中的每个元素answer[i]是在给出的单词列表 words 中可以作为字谜迷面puzzles[i]所对应的谜底的单词数目。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class L1178 {

    public static void main(String[] args) {

        String[] words = {"aaaa","asas","able","ability","actt","actor","access"};
        String[] puzzles = {"aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"};
        List<Integer> numOfValidWords = findNumOfValidWords1(words, puzzles);
        numOfValidWords.stream().forEach(System.out::print);
    }

    // 暴力方法，超出了时间限制
    public static List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < puzzles.length; i++) {

            int num = 0;
            for (int j = 0; j < words.length; j++) {

                if (words[j].contains(puzzles[i].charAt(0)+"")){
                    for (int k = 0; k < words[j].length(); k++) {
                        if (!puzzles[i].contains(words[j].charAt(k)+"")) {
                            num++;
                            break;
                        }
                    }
                }else {
                    num++;
                }


            }
            list.add(words.length - num);
        }

        return list;
    }


    /*
    官方答案
    方法一：二进制状态压缩
        思路与算法
        由于题目中规定 word 和 puzzle 均只包含小写字母，
        因此 Sw和 Sp的大小最多为26，我们可以考虑使用一个长度为 26 的二进制数 bw或 bp	来表示这一集合。

        因此我们可以使用一个哈希映射来表示需要的「数据结构」：对于哈希映射中的每一个键值对，其中的键表示一个长度为 26 的二进制数，值表示其出现的次数，
        即数组 words 中多少个 word 压缩成的二进制数等于键。构造哈希映射的过程也很简单：我们只需要遍历每一个 word，并遍历
        word 中的每一个字母，将对应位置的二进制位标记为 1，这样就计算出了 word 对应的二进制表示，将其在哈希映射中作为键对应的值增加 1 即可。

        对于 puzzle 对应的 bp，我们可以通过相同的方法求出，那么接下来就需要枚举 bp的子集 bp′了。枚举一个二进制数的子集也有多种方法，这里介绍常用的两种：
        第一种：由于题目中规定 puzzle 的长度恰好为 7，因此我们可以枚举所有 6 位的二进制
            （因为 puzzle 中的首字母必须要出现，因此最高位必须是 1，我们只需要枚举剩余的 6 位就行了）。
            对于每个枚举出的 6 位二进制数，我们遍历 puzzle 中除了首字母以外的其余 6 个字母，只有当二进制位为 1 时，
            我们才将 puzzle 中的字母在二进制表示中的二进制位标记位 1。这样我们就得到了每一个 bp′对应的二进制表示。
        第二种：我们也可以使用通用的「枚举二进制子集」的方法，下面给出伪代码：
            function get_subset(bitmask)
                subset = bitmask
                answer = [bitmask]
                while subset != 0
                    subset = (subset - 1) & bitmask
                    put subset into the answer list
                end while
                return answer
            end function
            其中 bitmask 表示一个二进制数，subset 会遍历所有 bitmask 的子集，并将所有的子集放入 answer 中。
            需要注意的是，bitmask 本身也是 bitmask 的一个子集，因此 answer 在初始时就包含 bitmask 本身。
            第一种方法类似，我们需要保证 puzzle 中的首字母必须要出现，因此在使用第二种方法枚举子集时，我们先将首字母对应的二进制位标记为 0，
            每枚举到一个子集，就将首字母对应的二进制位标记为 1，这样得到的子集都是满足要求的

     方法二：字典树


    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/solution/cai-zi-mi-by-leetcode-solution-345u/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static List<Integer> findNumOfValidWords1(String[] words, String[] puzzles) {
        Map<Integer, Integer> frequency = new HashMap<Integer, Integer>();

        for (String word : words) {
            int mask = 0;
            for (int i = 0; i < word.length(); ++i) {
                char ch = word.charAt(i);
                mask |= (1 << (ch - 'a'));
            }
            if (Integer.bitCount(mask) <= 7) {
                frequency.put(mask, frequency.getOrDefault(mask, 0) + 1);
            }
        }

        Set<Integer> integers = frequency.keySet();
        for (Integer i : integers) {
            System.out.println(i + ":" + frequency.get(i));
        }


        List<Integer> ans = new ArrayList<Integer>();
        for (String puzzle : puzzles) {
            int total = 0;

            // 枚举子集方法一
            // for (int choose = 0; choose < (1 << 6); ++choose) {
            //     int mask = 0;
            //     for (int i = 0; i < 6; ++i) {
            //         if ((choose & (1 << i)) != 0) {
            //             mask |= (1 << (puzzle.charAt(i + 1) - 'a'));
            //         }
            //     }
            //     mask |= (1 << (puzzle.charAt(0) - 'a'));
            //     if (frequency.containsKey(mask)) {
            //         total += frequency.get(mask);
            //     }
            // }

            // 枚举子集方法二
            int mask = 0;
            for (int i = 1; i < 7; ++i) {
                mask |= (1 << (puzzle.charAt(i) - 'a'));
            }
            int subset = mask;
            do {
                int s = subset | (1 << (puzzle.charAt(0) - 'a'));
                if (frequency.containsKey(s)) {
                    total += frequency.get(s);
                }
                subset = (subset - 1) & mask;
            } while (subset != mask);

            ans.add(total);
        }
        return ans;
    }



}
